package Algorithm.slidingWindow;

import java.util.HashMap;

/**
 * 3. 无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 * 题目简述：给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
 */
public class LongestSubstringWithoutRepeatingCharacters {

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring(" "));
    }

    /**
     * 思路：滑动窗口。窗口定义为当前以窗口左边界为起点的最长不重复子串，初始窗口为[0,0]。用一个map记录不重复元素的最新位置。
     * 开始扫描：1.维护窗口，当遇到重复元素时，若其前一个位置在left左边，即在窗口外则不用管，否则更新left为前重复元素位置+1
     *         2.维护map 3.更新最大窗口长度
     * 循环中先维护窗口，再计算窗口长度。
     */
    public static int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0, left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){ //1. 维护窗口
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i); //2. 维护map
            max = Math.max(max,i-left+1); //3. 更新最大窗口长度
        }
        return max;

    }

    public static int lengthOfLongestSubstring2(String s) {
        //先想出一个解法，再看有没有信息冗余的操作，逐步优化
        int maxLength = 0;
        HashMap<Character, Integer> subStringMap= new HashMap<>();
        for (int i=0;i < s.length();i++) {
            if(!subStringMap.containsKey(s.charAt(i))) {
                subStringMap.put(s.charAt(i), i);
            } else {
                if(maxLength < subStringMap.size()) {
                    maxLength = subStringMap.size();
                }
                int repeatIndex = subStringMap.get(s.charAt(i));
                subStringMap.clear();
                for(int j=repeatIndex+1;j <= i;j++) {
                    subStringMap.put(s.charAt(j), j);
                }
            }
        }
        //循环结束后看有没有特殊情况需要处理
        if(maxLength < subStringMap.size()) {
            maxLength = subStringMap.size();
        }
        return maxLength;
    }
}
